package me.seu.demo.algorithms;

import java.util.Arrays;

/**
 * (二路)归并排序
 *
 * @author liangfeihu
 * @since 2021/2/19 下午4:47
 */
public class MergeSort {

    public static int[] sort(int[] sourceArray) {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        if (arr.length < 2) {
            return arr;
        }

        int middle = (int) Math.floor(arr.length / 2);

        int[] left = Arrays.copyOfRange(arr, 0, middle);
        int[] right = Arrays.copyOfRange(arr, middle, arr.length);

        return merge(sort(left), sort(right));
    }

    private static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        int l = 0, r = 0, len = 0;
        while (len < left.length + right.length) {
            if (left[l] <= right[r]) {
                result[len++] = left[l++];

                if (l == left.length) {
                    for (int i = r; i < right.length; i++) {
                        result[len++] = right[r++];
                    }
                }
            } else {
                result[len++] = right[r++];

                if (r == right.length) {
                    for (int i = l; i < left.length; i++) {
                        result[len++] = left[l++];
                    }
                }
            }
        }
        return result;
    }

    public static void mergeSort(int[] array) {
        int length = array.length;
        if (length < 2) {
            return;
        }
        mergeSort(array, 0, length - 1);
    }

    private static void mergeSort(int[] array, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = (left + right) / 2;

        mergeSort(array, left, mid);
        mergeSort(array, mid + 1, right);

        merge(array, left, mid, right);
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int[] copyArray = Arrays.copyOfRange(array, left, right + 1);
        int l = left;
        int r = mid + 1;
        for (int k = left; k <= right; k++) {
            if (l > mid) {
                array[k] = copyArray[r - left];
                r++;
            } else if (r > right) {
                array[k] = copyArray[l - left];
                l++;
            } else if (copyArray[l - left] <= copyArray[r - left]) {
                array[k] = copyArray[l - left];
                l++;
            } else {
                array[k] = copyArray[r - left];
                r++;
            }
        } // end for

    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 6, 5, 7, 3, 6, 8, 9, 10, 0};
        System.out.println(Arrays.toString(arr));
        int[] sort = sort(arr);
        System.out.println(Arrays.toString(sort));

        int[] arr2 = new int[]{1, 3, 5, 2, 6, 5, 3, 8, 9, 10, 0};
        System.out.println(Arrays.toString(arr2));
        mergeSort(arr2);
        System.out.println(Arrays.toString(arr2));
    }


}
